package midalgorithms.dynamicplanning;

public class _01JumpGame {
    public static boolean canJump(int[] nums) {
        //  动态规划
        //  dp[i]表示在下标i处最多能往后跳的步数
        //  如果 i + dp[i] >= nums.length - 1 说明可以达到目标位置
        //  dp[i] = Math.max(dp[i-1] - 1,nums[i])
        //  如果中途的 dp[i] == 0 则失败
        if (nums.length <= 1){
            return true;
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int i = 0;
        while (dp[i] != 0 && i++ < dp.length){
            dp[i] = Math.max(dp[i-1] - 1,nums[i]);
            if (i + dp[i] >= nums.length - 1){
                return true;
            }
        }
        return false;
    }
}
